In circuit simulations of very large circuits, i.e. of circuits with a very large number of elements, a serial processing, i.e. calculation of the circuit parameters by a computer, is very time consuming. Even vector processors, which are rather expensive in their operation, require an immense demand in computing capacity and in time for calculating the electrical descriptive parameters for a circuit comprising a few 100,000 transistors.
For this reason, to avoid the serial execution of a circuit simulation, the electrical circuit can be divided into a plurality of parts, which are then respectively processed by different computers, or respectively, processors, which leads to a parallel execution of the circuit simulation.
However, in order to achieve an optimally good parallelization of the calculation of an electrical circuit descriptive parameters for the electrocircuit, it is very advantageous to consider two criteria in the partitioning of the electrical circuit into a plurality of parts. It is of considerable importance that all formed partitions of the electrical circuit are optimally equally large, in order to thereby enhance the effect that can be achieved by the parallelization. If one partition is larger than the other partitions by orders of magnitude, then the processing of the significantly larger partition in turn requires a much greater computing outlay than the processing of the other partitions. It is also important in the partitioning that optimally only a small number of connections exists between the individual partitions, since in the known methods for xe2x80x9cparallelizedxe2x80x9d circuit simulation, the required transmission capacity, i.e. the required communication between the computers, or respectively, processors which respectively process a partition, rises with an increasing number of existing connections between the partitions.
A language for the textual description of an electrical circuit which can be processed by a computer is the circuit simulation language SPICE. One document disclosing SPICE is I. Hoefer, et al., SPICE Analyseprogramm fur electronische Schaltungen, Springer, Berlin (1985), pp. 7-22.
The documents U. Kleis, et al., Doman Decomposition Methods for Circuit Simulation, Proceedings of the 8th Workshop on Parrallel and Distributed Simulation, PADS, Edinburgh, UK (July, 1994), pp. 183-86 U. Wever, et al., Parallel Transient Analysis for Circuit Simulation, Proceedings of the 29th Annual Hawaii International Conference on System Sciences (1946), pp. 442-47 teach how a parallelized circuit simulation can be executed, provided there is an arbitrary number of partitions of the electrical circuit. The manner in which partitions can be calculated is not described in these documents.
The documents B. Reiss, Partitioning Very Large Circuits Using Analytical Placement Techniques, Proceedings of the 31st ACM/IEEE Design Automation Conference (1994), pp. 646-51 J. Li, et al., New Spectral Linear Placement and Clustering Approach, 33rd Design Automation Conference, Las Vegas Jun. 3-7, 1996), pp. 88-93 teach a global partitioning method on what is known as the logic level, which is also referred to as the gate level.
On the logic level, discrete events are described with which it is not possible, however, to describe constantly dynamic characteristics of an electrical circuit on what is known as the transistor level, i.e. on the actual physical level of the electrical circuit.
The results of a circuit simulation which occurs on the logic level are thus unreliable and imprecise for some applications, since an exact time characteristic, which occurs in the electrical circuit, of the electrical signals cannot be taken into account either.
Furthermore, a model description of the individual gates is needed for the circuit simulation on the gate level, whereby the circuit description with transistor models is already present for the simulation on the transistor level. The model description must be calculated before the method can be executed on the gate level.
What is known as the conjugation gradient method is taught by document G. Sigl, Analytical Placement: A Linear or a Quadratic Objective Function?, Proceedings of the 28th ACM/IEEE DAC (1991), pp. 427-432.
An overview of various partitioning specifications can be found in P. Johannes, Partioning of VLSI Circuits and Systems, 33rd Design and Automation Conference, Las Vegas (Jun. 3-7, 1996), pp. 83-87.
An object of the present invention is to provide a method for partitioning an electrical circuit which directly accounts for the elements of the electrical circuit on the transistor level.
To that end, in an embodiment in the invention provides a computer supported method for partitioning an electrical circuit,
wherein the electrical circuit is mapped on a graph having the same topology as the electrical circuit,
wherein nodes and/or edges of the graph are assigned weight values with which a required computing outlay, for the calculation of electrical descriptive parameters for elements of the electrical circuit which are represented by the respective node and/or by the respective edge, is described,
wherein a method for placing the elements of the electrical circuit is applied to the elements.
wherein, in the method for placing the elements, a total length of couplings between the elements is minimized, the weight values that are assigned to the nodes and/or edges being taken into account,
wherein, for the electrical circuit, a measure is calculated of a number of arising cut edges and/or arising margin nodes of partitions of the electrical circuit in the partitioning, and
wherein the elements are grouped in partitions depending on the measure.
In this method, the electrical circuit is mapped on a graph which comprises the same topology as the electrical circuit. The edges and/or nodes of the graph are weighted with weight values which describe an approximately required computing outlay for the calculation of electrical descriptive parameters for the electrical circuit element that is respectively represented by the edge and/or node.
The partitions for the electrical circuit in the graph are formed in such a way that a method for placing the elements of the electrical circuit is applied to the elements, in which method a total length of couplings between the elements in the electrical circuit is minimized. In addition, a measure of the number of appearing edge nodes and/or cut edges of partitions which would respectively appear given the partitioning is calculated for the electrical circuit. The partitions are formed depending on the measure in that the elements are grouped into the individual partitions.
The method has some appreciable advantages compared to the method set forth in B. Reiss, Partitioning Very Large Circuits Using Analytical Placement Techniques, Proceedings of the 31st ACM/EEE Design Automation Conference (1994) pp. 664-651.
Since the method operates directly on the transistor level of the electrical circuit, the results achieved by the method in a later circuit simulation using the inventively calculated partitions are appreciably more precise and more reliable.
In an embodiment of the invention, at the beginning of the method, a grouping of elements of the electrical circuit is executed, for which it is specified that these elements are jointly assigned to one partition.
In an embodiment of the invention, in the grouping of the elements of the electrical circuit, at least one of the following specifications is applied:
elements of a controlled source, at least one controlling element, and the controlled source are jointly assigned to one partition,
connection loops in the electrical circuit, they are jointly assigned to one partition, shorts must not arise due to the partitioning and/or due to a modelling of an interface.
In an embodiment of the invention, a plurality of nodes and/or edges of the graph are assigned a common weight value.
In an embodiment of the invention, the graph of the partition is mapped onto the electrical circuit, whereby the partition comprises the elements of the electrical circuit according to the executed partitioning.
In an embodiment of the invention, a plurality of partitions are formed by multiple execution of the method, and wherein the electrical descriptive parameters for the elements of the electrical circuit are calculated for each partition, at least a part of the partitions being processed on a plurality of computers and/or processors in parallel fashion.
In an embodiment of the invention, the parallel processing of the partitions is centrally controlled.
In an embodiment of the invention, at least a part of the partitions is centrally controlled in such a way that all the terminals of the respective partition are coupled only with a central control unit, and a transmission of data thus occurs only between the central control unit and at least the part of the partitions.
In an embodiment of the invention, at least a part of the terminals of the respective partition are additionally assigned a voltage source, the value of which is prescribed by the central control unit during the calculation of the electrical descriptive parameters.
In an embodiment of the invention, at least a part of the terminals of the respective partition is additionally assigned a resistor.
In an embodiment of the invention, the measure of the number of arising cut edges and/or arising margin modes is formed according to the following specification:       RC    =                  C        LR                              "LeftBracketingBar"          L          "RightBracketingBar"                ·                  "LeftBracketingBar"          R          "RightBracketingBar"                      ,
wherein
RC designates the measure of the number of arising cut edges and/or arising margin nodes,
L designates a first partition,
R designates a second partition,
CLR designates a number of couplings of the first partition with the second partition,
|L| designates a weighted number of elements which the first partition contains,
|R| designates a weighted number of elements which the second partition contains.
For predeterminable elements of the electrical circuit, it is advantageous to specify at the beginning of the method that the elements are grouped together into one partition. It is possible to guarantee on the basis of this further development that, for example, given controlled sources, both the controlling elements and the controlled sources can be processed together in one partition. Likewise, it is also possible on the basis of this development to arrange together in one partition connection loops in the electrical circuit, which arise by means of the consecutive connection of voltage-defining elements such as voltage sources and inductivities. Furthermore, it is possible in this way to avoid shorts which may potentially occur due to the partitioning and the modelling of the interfaces.
On the basis of the development of the method that a plurality of edges and/or nodes of the graph are assigned a common weight value, the execution of the method by a computer is further accelerated, since, in this development, a lower number of weight values needs to be taken into account in the framework of the method.
It is also advantageous to form a plurality of partitions for the electrical circuit, to map the corresponding graphs of the partitions on the electrical circuit again for the partitions, and to process the arising partitions of the electrical circuit on different computers, or respectively, processors in parallel fashion. By means of this parallelization, a circuit simulation of a rather large circuit can be executed appreciably more rapidly than is possible in a purely xe2x80x9cserialxe2x80x9d circuit simulation.
It is also advantageous in the parallelized circuit simulation to control the processing of the individual partitions centrally. In this way, a controlled circuit simulation is realized with optimally little communication outlay.
It is also advantageous to additionally provide the individual terminals of the partitions that ate coupled with components not situated in the partition with a voltage source and a resistor, whereby the electrical marginal descriptive parameters are respectively assigned to the voltage source by a central control unit which controls the parallelized processing of the partitions. On the basis of the resistor which is provided in the terminals, the convergence of the circuit simulation during the parallelized circuit simulation is guaranteed, the value of which is dynamically adjusted by the control unit.
These and other features and aspects of the invention will become clear in the following detailed description of a few typical exemplary embodiments with reference to the accompanying drawings.